/*
 * @Author: szx
 * @Date: 2021-12-15 13:39:21
 * @LastEditTime: 2021-12-15 14:14:08
 * @Description:
 * @FilePath: \leetcode\100-199\145\145.js
 */
var postorderTraversal = function (root) {
    const res = [];
    const dfs = (node) => {
        if (node === null) return;
        dfs(node.left);
        dfs(node.right);
        res.push(node.val);
    };
    dfs(root);
    return res;
};

var postorderTraversal = function (root) {
    const res = [];
    if (root == null) return [];
    const stk = [];
    stk.push(root);
    while (stk.length != 0) {
        let tmp = stk.pop();
        res.push(tmp.val);
        if (tmp.left) stk.push(tmp.left);
        if (tmp.right) stk.push(tmp.right);
    }
    return res.reverse();
};
var postorderTraversal = function (root) {
    const res = [];
    if (root == null) return [];
    const stk = [];
    let prev = null;
    while (stk.length != 0 || root) {
        // 1.遍历到最左子节点
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        // 2.遍历最左子节点的右子树(右子树存在 && 未访问过)
        if (root.right && root.right != prev) {
            // 重复压栈以记录当前路径分叉节点
            stk.push(root);
            root = root.right;
        } else {
            // 后序：填充vec在node->left和node->right后面
            // 注意：此时node的左右子树应均已完成访问
            res.push(root.val);
            // 避免重复访问右子树[记录当前节点便于下一步对比]
            prev = root;
            // 避免重复访问左子树[设空节点]
            root = nullptr;
        }
    }
    return res;
};
